#pragma once
#include "../graphics.h"
#define N 120 // 数组元素个数

const COLORREF cr_fr = RGB(254,0,0); 
const COLORREF cr_fg = RGB(0,254,0); 
const COLORREF cr_fb = RGB(0,0,254); 
const COLORREF cr_fbk = RGB(0,0,0); 
//每个元素之间的间隔
const int gap = 10;
//每个元素的值虚乘的权重
const int W_value = 5;
//存储线的y坐标，方便排序时交换的绘图
int gposy[N];

//睡眠毫秒数
const int ms = 10;
// 睡眠i毫秒
void msleep(int i);

void BubbleSort(int a[], int l, int r,int num,int XRst,COLORREF cr);
void QuickSort(int a[], int l, int r,int num,int XRst,COLORREF cr);
void SelectSort(int a[], int l, int r,int num,int XRst,COLORREF cr);

//数组排序时的动画,i、j分别为两个元素下标，可通过其找到元素长度，绘画位置；第num个排序，XRst为分辨率/3
void animate(int arr[],int i,int j,int num,int XRst,COLORREF cr)
{
	//用黑线覆盖掉原来的位置
	line(num*XRst,i*gap,(num+1)*XRst,i*gap,cr_fbk);
	line(num*XRst,j*gap,(num+1)*XRst,j*gap,cr_fbk);

	//用cr颜色画新线
	line(num*XRst,i*gap,(num)*XRst+arr[i]*W_value,i*gap,cr);
	line(num*XRst,j*gap,(num)*XRst+arr[j]*W_value,j*gap,cr);
}

//交换两个元素，传入参数为指针
void swap(int* a, int* b)
{   
    
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
//左闭右闭区间[l,r]
void BubbleSort(int a[], int l, int r,int num,int XRst,COLORREF cr)
{
	for (int i = l; i <= r - 1; ++i)
	{
		for (int j = l; j <= r - i - 1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				swap(&a[j], &a[j + 1]);
				animate(a,j,j+1,num,XRst,cr);
				msleep(ms);
			}
		}
	}
    //printf("BubbleSort Compelete\n");

}
void QuickSort(int a[], int l, int r,int num,int XRst,COLORREF cr)
{
	if (l >= r)
    {
        //printf("QuickSort Compelete\n");
        return;
    }
	// if(r - l < 5)
	// {
	// 	SelectSort(a, l, r,num,XRst,cr);
	// }
	int keyi = l, left = l, right = r;
	while (left < right)
	{
		while (a[right] >= a[keyi] && left < right)--right;
		while (a[left] <= a[keyi] && left < right)++left;


		if(left != right)
		{
			swap(&a[left], &a[right]);
			animate(a,left,right,num,XRst,cr);
			msleep(ms);
		}

	}
	if(left != keyi)
	{
		swap(&a[left], &a[keyi]);
		animate(a,left,keyi,num,XRst,cr);
		msleep(ms);
	}

	int mid = left;
	//[l,mid][mid+1,r]
    //sleep(3);
	QuickSort(a, l, mid,num,XRst,cr);
	QuickSort(a, mid + 1, r,num,XRst,cr);

}


void SelectSort(int a[], int l, int r,int num,int XRst,COLORREF cr)
{
	for (int i = l; i <= r - 1; ++i)
	{
        //找出最小元素
		int mini = i;
		for (int j = i; j <= r; ++j)
		{
            if(a[j] < a[mini])
			mini = j;
		}
		swap(&a[i], &a[mini]);
		animate(a,i,mini,num,XRst,cr);
		msleep(ms);
	}
}


//[begin,end]表示画的数组的范围，左闭右闭区间,第num个排序，XRst为分辨率/3
void draw(int arr[],int begin,int end,int num,int XRst,COLORREF cr)
{ 
	
	//数组元素颜色
	// COLORREF cr = RGB(254,0,0);
	//COLORREF cr = RGB(0,254,0);
	// (void)cr;
	

	for(int i = begin ,pos = 0; i <= end ; i+= 1 ,pos += gap)
	{	
		// line(num*XRst,pos,num*XRst+arr[i]*20,pos,cr);
		line(num*XRst,i*gap,num*XRst+arr[i]*W_value,i*gap,cr);
		// msleep(1000);
		gposy[i] = pos;
	}
	// exit_graphic();

}